#include<bits/stdc++.h>
using namespace std;
class un
{
    vector<int> f;
public:
    int c;
    bool flag;
    un(int n)
    {
        flag=true;
        c=n;
        f=vector<int>(n);
        for(int i=0;i<n;i++)
            f[i]=i;
    }
    int find(int x)
    {
        if(f[x]!=x)
            f[x]=find(f[x]);
        return f[x];
    }
    bool merge(int x,int y,int k)
    {
        int a=find(x);
        int b=find(y);
        if(k==0)
        {
            if(a!=b)
            {
                c--;
                f[a]=b;
                return true;
            }
            return false;
        }
        else
        {
            if(a==b) flag=false;
            c--;
            f[a]=b;
            return true;
        }
    }
};

class Solution {
public:
    int maxStability(int n, vector<vector<int>>& edges, int k) {
        un ui(n);
        int m=edges.size();
        priority_queue<int,vector<int>,greater<>> l;
        priority_queue<int,vector<int>,greater<>> l1;
        priority_queue<int,vector<int>,greater<>> l2;
        for(int i=0;i<m;i++)
        {
            if(edges[i][3]==1)
            {
                ui.merge(edges[i][0],edges[i][1],edges[i][3]);
                l.push(edges[i][2]);
            }    
        }
        if(!ui.flag) return -1;
        sort(edges.begin(),edges.end(),[](vector<int>& v1,vector<int>& v2)
        {
            return v1[2]>v2[2];
        });
        for(auto& row:edges)
        {
            int x=row[0],y=row[1],w=row[2],p=row[3];
            if(p==0)
            {
                if(ui.merge(x,y,p))
                    l1.push(w);
            }
        }
        if(l1.size()!=0)
        {
            while(!l1.empty()&&k>0)
            {
                int v=l1.top();
                l1.pop();
                l2.push(v*2);
                k--;
            }
        }
        while(!l1.empty())
        {
            int v=l1.top();
            l2.push(v);
            l1.pop();
        }
        if(ui.c!=1) return -1;
        if(l.size()==0) return l2.top();
        if(l2.size()==0) return l.top();
        return min(l.top(),l2.top());
    }
};

int main()
{
    vector<vector<int>> vec={{0,1,2077,0},{2,4,31376,1},{3,4,36289,0},{0,3,78084,1},{2,3,89506,1},{0,2,82142,0}};
    Solution so;
    so.maxStability(5,vec,5);
    return 0;
}